package com.itheima.algorithm.divideandconquer;

/**
 * <h3>快速幂 - 分治</h3>
 */
public class QucikPowLeetcode50 {

    // 求 2^16
    static double myPow(double x, int n) {
        long p = n; // -2
        if (0 > p) {
            p = -p; // -2147483648  2147483647
        }
        double r = myPowPostive(x, p);
        return 0 > n ? 1 / r : r;
    }

    static double myPowPostive(double x, long n) {
        /*double mul = 1;
        for (int i = 0; i < n; i++) {
            mul *= x;
        }
        return mul;*/
        if (0 == n) {
            return 1.0;
        }
        if (1 == n) { // 减少不必要的依次递归
            return x;
        }

        double y = myPowPostive(x, n / 2);
        if (0 == (n & 1)) { // 偶数
            return y * y;
        } else { // 奇数
            return x * y * y;
        }
    }

    public static void main(String[] args) {
        System.out.println(myPow(2, 16)); // 65536
        System.out.println(myPow(2, 10)); // 1024
        System.out.println(myPow(2, 0)); // 1.0
        System.out.println(myPow(2, -2)); // 0.25 2^-2 = 1/2^2
        System.out.println(myPow(2, -2147483648)); // 1.0   int
        System.out.println(myPow(2.1, 3)); // 9.261
    }
}
